#pragma once

#include <deque>
#include <functional>
#include "../utils/misc.h"

namespace mdtx::online::container
{
    template <typename T, typename W, size_t N = 1>
    using wsnode = bind_ntuple<T, W, 1, N>;

    template <typename T, typename W, size_t N = 1, typename C = std::less<T>, typename CW = std::less<W>, typename A = std::allocator<T>>
    class wsdeque : public std::deque<wsnode<T, W, N>, typename std::allocator_traits<A>::template rebind_alloc<wsnode<T, W, N>>>
    {
        using base = std::deque<wsnode<T, W, N>, typename std::allocator_traits<A>::template rebind_alloc<wsnode<T, W, N>>>;

    public:
        using typename base::value_type;
        using weight_type = W;
        struct value_compare
        {
            constexpr bool operator()(value_type const &lhs, value_type const &rhs) const
            {
                return C{}(std::get<0>(lhs), std::get<0>(rhs));
            }
        };
        using typename base::size_type;
        using typename base::const_iterator;
        using typename base::const_reference;

    protected:
        static inline value_type make_node(T const &val)
        {
            value_type node{};
            std::get<0>(node) = val;
            return node;
        }

        template <typename Tup, size_t... Is>
        static inline void add_weight(Tup &found, Tup const &node, std::index_sequence<Is...>)
        {
            ((std::get<Is>(found) += std::get<Is>(node), 0), ...);
        }

        template <typename Tup, size_t... Is>
        static inline void sub_weight(Tup &found, Tup const &node, std::index_sequence<Is...>)
        {
            ((std::get<Is>(found) -= std::get<Is>(node), 0), ...);
        }

        static inline bool cmp_lte_weight(W const &w1, W const &w2)
        {
            return !CW{}(w2, w1);
        }

        template <size_t... Is>
        static inline bool lte_weight(value_type const &found, value_type const &node, std::index_sequence<Is...>)
        {
            return (cmp_lte_weight(std::get<Is>(found), std::get<Is>(node)) || ...);
        }

        constexpr static make_index_range<1, N> widx{};

    public:
        // Lookup

        const_iterator find(T const &val) const
        {
            value_type node = make_node(val);
            const_iterator it = std::lower_bound(base::cbegin(), base::cend(), node, value_compare{});
            if (it != base::cend() && !value_compare{}(node, *it))
            {
                return it;
            }
            else
            {
                return base::cend();
            }
        }

        const_iterator lower_bound(T const &val) const
        {
            value_type node = make_node(val);
            return std::lower_bound(base::cbegin(), base::cend(), node, value_compare{});
        }

        const_iterator upper_bound(T const &val) const
        {
            value_type node = make_node(val);
            return std::upper_bound(base::cbegin(), base::cend(), node, value_compare{});
        }

        std::pair<const_iterator, const_iterator> equal_range(T const &val) const
        {
            value_type node = make_node(val);
            return std::equal_range(base::cbegin(), base::cend(), node, value_compare{});
        }

        const_reference at(size_type pos) const
        {
            return base::at(pos);
        }

        const_reference operator[](size_type pos) const
        {
            return base::operator[](pos);
        }

        const_reference front() const
        {
            return base::front();
        }

        const_reference back() const
        {
            return base::back();
        }

        // Iterator

        const_iterator begin() const
        {
            return base::cbegin();
        }

        const_iterator end() const
        {
            return base::cend();
        }

        const_iterator rbegin() const
        {
            return base::crbegin();
        }

        const_iterator rend() const
        {
            return base::crend();
        }

        // Modifier

        const_iterator insert(value_type const &node)
        {
            auto it = std::lower_bound(base::begin(), base::end(), node, value_compare{});
            if (it != base::end() && !value_compare{}(node, *it))
            {
                add_weight(*it, node, widx);
            }
            else
            {
                it = base::insert(it, node);
            }
            return it;
        }

        const_iterator insert(value_type &&node)
        {
            auto it = std::lower_bound(base::begin(), base::end(), node, value_compare{});
            if (it != base::end() && !value_compare{}(node, *it))
            {
                add_weight(*it, node, widx);
            }
            else
            {
                it = base::insert(it, std::move(node));
            }
            return it;
        }

        template <typename... Args>
        const_iterator insert(Args &&...args)
        {
            return insert(value_type(std::forward<Args>(args)...));
        }

        void push_front(value_type const &node)
        {
            if (base::empty() || value_compare{}(node, base::front()))
            {
                base::push_front(node);
            }
            else
            {
                insert(node);
            }
        }

        void push_front(value_type &&node)
        {
            if (base::empty() || value_compare{}(node, base::front()))
            {
                base::push_front(std::move(node));
            }
            else
            {
                insert(std::move(node));
            }
        }

        template <typename... Args>
        void push_front(Args &&...args)
        {
            push_front(value_type(std::forward<Args>(args)...));
        }

        void push_back(value_type const &node)
        {
            if (base::empty() || value_compare{}(base::back(), node))
            {
                base::push_back(node);
            }
            else
            {
                insert(node);
            }
        }

        void push_back(value_type &&node)
        {
            if (base::empty() || value_compare{}(base::back(), node))
            {
                base::push_back(std::move(node));
            }
            else
            {
                insert(node);
            }
        }

        template <typename... Args>
        void push_back(Args &&...args)
        {
            push_back(value_type(std::forward<Args>(args)...));
        }

        void erase(T const &val)
        {
            auto node = make_node(val);
            auto it = std::lower_bound(base::begin(), base::end(), node, value_compare{});
            if (it != base::end() && !value_compare{}(node, *it))
            {
                base::erase(it);
            }
        }

        void erase(value_type const &node)
        {
            auto it = std::lower_bound(base::begin(), base::end(), node, value_compare{});
            if (it != base::end() && !value_compare{}(node, *it))
            {
                if (lte_weight(*it, node))
                {
                    base::erase(it);
                }
                else
                {
                    sub_weight(*it, node, widx);
                }
            }
        }

        template <typename... Args>
        void erase(Args const &...args)
        {
            erase(value_type(args...));
        }

        void erase_rank(size_type rank)
        {
            base::erase(base::begin() + rank);
        }

        template <typename Container>
        void merge(Container const &other)
        {
            for (auto const &node : other)
            {
                insert(node);
            }
        }

        using base::pop_back;
        using base::pop_front;

    private:
        using base::assign;
        using base::emplace;
        using base::emplace_back;
        using base::emplace_front;
        using base::resize;
    };
}
